package day07;

public class 删除并获得点数 {
    public int deleteAndEarn(int[] nums) {
        // 一定要先画图分析
        // 学会举一反三，联想到之前打家劫舍的问题
        // 将这个题进行数组下标映射
        int n = nums.length;
        int m = 0;
        for (int i = 0; i < n; i++) {
            m = Math.max(m, nums[i]);
        }
        int[] arr = new int[m + 1];
        for (int i = 0; i < n; i++) {
            int tmp = nums[i];
            arr[tmp] += tmp;
        }
        // 对arr数组进行打家劫舍的思想解决
        // 相邻的两个的数不能选
        int[] f = new int[m + 1];
        int[] g = new int[m + 1];
        // 初始化
        f[0] = arr[0];
        for (int i = 1; i < m + 1; i++) {
            f[i] = g[i - 1] + arr[i];
            g[i] = Math.max(f[i - 1], g[i - 1]);
        }
        return Math.max(f[m], g[m]);
    }
}
